Boolean algebra is an important aspect of computer science and digital system design. For example, many problems in computer-aided design for digital circuits can be solved through the use of Boolean functions. Thus, the efficient symbolic representation and manipulation of Boolean functions in the memory of a computer system is important.
One technique for representing a Boolean function is the use of a binary decision diagram (BDD). A BDD is a directed acyclic graph with each non-terminal node labeled with a Boolean variable and having a 0-branch and a 1-branch, corresponding to the value of the Boolean variable. Nodes which are directly connected to the 0-branch and 1-branch of a higher level node are called the child nodes of the higher level node. The higher level node is called the parent node of the child nodes. The BDD also has terminal nodes, which are labeled 0 or 1, representing the constant Boolean functions 0 and 1. An example of a BDD 100 representing the Boolean function X*Y+Z (* represents the Boolean operator AND; + represents the Boolean operator OR) is shown in FIG. 1. The BDD 100 has three non-terminal nodes, X , Y and Z, and terminal nodes 0 and 1. Nodes are represented herein as follows: a node with label x having a 0-branch child y and 1-branch child z, is represented by the notation node (x,y,z).
An ordered binary decision diagram (OBDD) is a BDD with the constraint that the input variables are ordered such that the traversal of any branch of the BDD will result in visiting the variables in the given order. Thus, given a variable ordering of X,Y,Z, the BDD 100 in FIG. 1 is ordered because the traversal of any of the branches of the BDD will result in visiting the variables in the given order. Finally, a reduced ordered binary decision diagram (ROBDD) is an OBDD where each node represents a distinct logic function. As used hereinafter, the term BDD refers to a ROBDD.
The use of BDD's for the efficient processing of Boolean functions is described in detail in R. Bryant, Graph-Based Algorithms for Boolean Function Manipulation, IEEE Transactions On Computers, Vol. C-35, No. 8, August 1986; and K. Brace, R. Rudell, and R. Bryant, Efficient Implementation of a BDD Package, paper 3.1, 27.sup.th ACM/IEEE Design Automation Conference, 1990; both of which are incorporated herein by reference. Thus, the details of the use of BDD's for processing Boolean functions is well known to those skilled in the art and will not be described in detail herein.
One problem with the use of the known techniques for representing and manipulating BDD's during the processing of Boolean functions in a computer system is that performance of the computer system may become slow because of the large number of main memory accesses required. Main memory has slow access time relative to the speed of the central processing unit. The use of cache memory can sometimes improve processing speeds when sequential main memory accesses are made to memory locations which are near to each other. However, one of the problems with the known BDD representation and manipulation techniques is that there may be many sequential main memory accesses to locations which are in widely disparate memory locations. This results in many cache misses, further slowing the overall processing speed.
Additionally, during the processing of BDD's which are stored in the memory of the computer system, it is often required to create a new BDD in memory. During the creation of the new BDD, various nodes will be created. If the same node is to be created more than once, it is desirable to refer to the already created node rather than to create a duplicate of an existing node, thereby saving memory space. In accordance with known techniques, each time a new node is created in memory, an entry is made in a hash table. The hash table entry contains a pointer to the memory location in which the newly created node is located. Thus, when a new node is about to be created, the hash key of the new node is computed and the hash table entry corresponding to the computed hash key is interrogated. The node in the memory location contained in the hash table entry is retrieved from main memory to determine whether the stored node is the same as the node that is about to be created.
However, as a result of the general properties of hash tables, various unrelated nodes may have the same hash key and will therefore be assigned the same entry in the hash table. Thus, a single hash table entry may be linked to various memory locations. As a result, when a particular node is being searched for, each of the nodes with the same hash key must be retrieved from memory in order to determine whether they match the desired node. Each of these memory accesses slows the performance of the system.
In view of the current state of the art in high speed central processing units, the biggest performance bottleneck in the known BDD computer packages is the relatively long latency of main memory. Thus, each access to main memory severely impairs the processing speed of the computer while performing BDD manipulation.